package LeetCode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class LC_587_ErecttheFence {

    public static void main(String[] args) {

    }

    class Point {
        int x;
        int y;

        Point() {
            x = 0;
            y = 0;
        }

        Point(int a, int b) {
            x = a;
            y = b;
        }
    }

    class Solution {
        public List<Point> outerTrees(Point[] points) {
            Point first = points[0];
            int firstIndex = 0;
            for (int i = 0; i < points.length; i++) {
                Point point = points[i];
                if (point.x < first.x) {
                    first = point;
                    firstIndex = i;
                }
            }
            Set<Point> answer = new HashSet<>();
            Point cur = first;
            int curIndex = firstIndex;
            answer.add(first);
            do {
                Point next = points[0];
                int nextIndex = 0;
                for (int i = 1; i < points.length; i++) {
                    if (i == curIndex)
                        continue;
                    Point p = points[i];
                    int cross = crossProductLength(p, cur, next);
                    if (nextIndex == curIndex || cross > 0 || (cross == 0 && distance(p, cur) > distance(next, cur))) {
                        next = p;
                        nextIndex = i;
                    }
                }
                for (int i = 0; i < points.length; i++) {
                    Point p = points[i];
                    int cross = crossProductLength(p, cur, next);
                    if (i != curIndex && cross == 0) {
                        answer.add(p);
                    }
                }
                cur = next;
                curIndex = nextIndex;
            } while (curIndex != firstIndex);

            return new ArrayList<>(answer);
        }

        private int crossProductLength(Point A, Point B, Point C) {
            int BAx = A.x - B.x;
            int BAy = A.y - B.y;
            int BCx = C.x - B.x;
            int BCy = C.y - B.y;
            return (BAx * BCy - BAy * BCx);
        }

        private int distance(Point p1, Point p2) {
            return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
        }

    }
}